package algorithm.sort;

import com.alibaba.fastjson.JSON;

import java.util.Arrays;

public class InsertSort{


    public static void main(String[] args) {
        // 插入排序--简单插入排序，抓扑克牌，插牌，每次都往有顺序的序列插入符合顺序的新牌
        // 选定一个目标，交换方式实现，与冒泡有什么区别？ 冒泡排序找每趟的最大数，插入排序先右移后插入
        // 从小到大排序
        deductionInsert();
        System.out.println("==============");
        int[] arr = TestHelp.random(100000);
        int[] arrCopy = Arrays.copyOfRange(arr,0,20);
        TestHelp.print("比较前",arr);
        long begin = TestHelp.begin();
        insert(arr);
        TestHelp.end(begin);
        TestHelp.print("比较后",arr);
        System.out.println("===========交换方式的插入排序=================");
        deductionInsertSwap();
        insertSwap(arrCopy);

    }

    /**
     * 插入排序
     * 时间复杂度O(n^2)
     * 空间复杂度O(1)，只需要一个临时变量
     * 稳定，相同元素的位置不会变换，没有大于等于比较，也没有二分查找
     */
    public static void insert(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int waitInsertVal = arr[i];// 将要插入的值
            int waitInsertIndex = i - 1 ;// 将要插入的位置

            // 判断将要插入的位置是否可以插入
            while(waitInsertIndex >= 0 && waitInsertVal < arr[waitInsertIndex]){
                // 先右移
                arr[waitInsertIndex+1] = arr[waitInsertIndex];
                waitInsertIndex--;// 将要插入的位置索引向左移，找上一个元素
            }
            arr[waitInsertIndex+1] = waitInsertVal;// 由于将要插入的位置索引在循环中已经向左移了，再加上1，则是正确插入位置
            //TestHelp.print("第"+i+"趟",arr);
        }

    }

    /**
     * 逐步推导，演绎，先从第二个元素，第三个元素。。一个个元素排序处理
     * 右移后插入
     */
    public static void deductionInsert(){
        int[] arr = new int[]{8,3,12,6,19,2};

        // 第一趟============
        int waitInsertVal = arr[1];// 将要插入的值
        int waitInsertIndex = 1 - 1 ;// 将要插入的位置

        // 判断将要插入的位置是否可以插入
        while(waitInsertIndex >= 0 && waitInsertVal < arr[waitInsertIndex]){
            // 先右移
            arr[waitInsertIndex+1] = arr[waitInsertIndex];
            waitInsertIndex--;// 将要插入的位置索引向左移，找上一个元素
        }
        arr[waitInsertIndex+1] = waitInsertVal;// 由于将要插入的位置索引在循环中已经向左移了，再加上1，则是正确插入位置
        TestHelp.print(arr);
        // 第二趟===========
        waitInsertVal = arr[2];// 将要插入的值
        waitInsertIndex = 2 - 1 ;// 将要插入的位置
        // 判断将要插入的位置是否可以插入
        while(waitInsertIndex >= 0 && waitInsertVal < arr[waitInsertIndex]){
            // 先右移
            arr[waitInsertIndex+1] = arr[waitInsertIndex];
            waitInsertIndex--;// 将要插入的位置索引向左移，找上一个元素
        }
        arr[waitInsertIndex+1] = waitInsertVal;// 由于将要插入的位置索引在循环中已经向左移了，再加上1，则是正确插入位置
        TestHelp.print(arr);
    }

    /**
     * 逐步推导，交换方式,确保每一次插入后的左边的顺序的都是正确的，右边的数据指待插入的数据[1][n-1],[2][n-2] ...左边都是排好序的，右边都是待排序数据
     */
    public static void deductionInsertSwap(){
        int[] arr = new int[]{8,3,12,6,19,2};
        // 第一趟  (8,3) =》（3,8）

        // 第二趟 （3,8,12）=》（3,8,12）

        // 第三趟 （3,8,12,6）=》（3,6,8,12）

        // 第四趟 （3,6,8,12,19）=》（3,6,8,12,19）

        // 第五趟  （3,6,8,12,19,2）=》（2,3,6,8,12,19）
        // ================================================
        // 第一趟  (8,3) =》（3,8）
        int j = 1;
        if(arr[j]<arr[j-1]){
            TestHelp.swap(arr,j,j-1);
        }
        TestHelp.print("第一趟",arr);
        // 第二趟 （3,8,12）=》（3,8,12）
        j = 2;
        for (int k = j; k >0 ; k--) {
            if(arr[k]<arr[k-1]){
                TestHelp.swap(arr,k,k-1);
            }
        }
        TestHelp.print("第二趟",arr);
        // 第三趟 （3,8,12,6）=》（3,6,8,12）
        j = 3;
        for (int k = j; k >0 ; k--) {
            if(arr[k]<arr[k-1]){
                TestHelp.swap(arr,k,k-1);
            }
        }
        TestHelp.print("第三趟",arr);

    }

    /**
     * 直接插入，交换方式,确保每一次插入后的左边的顺序的都是正确的，右边的数据指待插入的数据[1][n-1],[2][n-2] ...左边都是排好序的，右边都是待排序数据
     */
    public static void insertSwap(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            for (int k = i; k >0 ; k--) {
                if(arr[k]<arr[k-1]){
                    TestHelp.swap(arr,k,k-1);
                }
            }
            TestHelp.print("第"+i+"趟",arr);
        }

    }
}
